/*
题目: 滑动谜题
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

https://leetcode.cn/problems/sliding-puzzle/
 */
public class SlidingPuzzle {
    int[] dir = new int[] {-3, 3, 1, -1}; // 方向
    String tar = "123450"; // 目标字符串
    private static class Pair {
        String str ;
        int index ;  // 零 的 位置
        public Pair(String str, int index) {
            this.str = str;
            this.index = index;
        }
    }

    // 转化成一维, 进行交换
    public int slidingPuzzle(int[][] board) {
        // 双向广搜 -- 优化
        char[] initCs = new char[6];   // 初始情况
        int zeroPos = 0;// 指向 0 的位置
        for (int i = 0, k = 0; i < 2; i ++) {
            for (int j = 0; j < 3; j ++) {
                initCs[k ++] = (char) (board[i][j] + '0');
                if (board[i][j] == 0)   zeroPos = 3 * i + j;  // 初始情况 0 的位置
            }
        }
        String initStr = new String(initCs);
        if (initStr.equals(tar))    return 0;

        Queue<Pair> frontQue = new LinkedList<> ();
        Queue<Pair> backQue = new LinkedList<> ();
        Map<String, Integer> frontMap = new HashMap<> ();
        Map<String, Integer> backMap = new HashMap<> ();

        frontQue.offer(new Pair(initStr, zeroPos));
        backQue.offer(new Pair(tar, 5));
        frontMap.put(initStr, 0);
        backMap.put(tar, 0);

        while (!frontQue.isEmpty() && !backQue.isEmpty()) {
            int ret = -1;
            if (frontQue.size() <= backQue.size()) {
                ret = update(frontQue, frontMap, backMap);
            } else {
                ret = update(backQue, backMap, frontMap);
            }

            if (ret != -1)  return ret;
        }

        return -1;
    }

    private int update(Queue<Pair> queue, Map<String, Integer> map, Map<String, Integer> another) {
        int size = queue.size();
        while (size -- > 0) {
            Pair cur = queue.poll();
            String curStr = cur.str;
            char[] curCs = curStr.toCharArray();
            int zeroPos = cur.index, steps = map.get(curStr); // 0 所在的下标 并 获取到此处的位置

            for (int i = 0; i < 4; i ++) {
                int nextPos = zeroPos + dir[i];
                if (nextPos < 0 || nextPos > 5 || (zeroPos == 2 && nextPos == 3) || (zeroPos == 3 && nextPos == 2)) continue ;

                swap(curCs, zeroPos, nextPos);
                String nextStr = new String(curCs);
                if (map.containsKey(nextStr)) {
                    swap(curCs, zeroPos, nextPos);
                    continue ;
                }
                if (another.containsKey(nextStr)) {
                    return steps + another.get(nextStr) + 1;
                } else {
                    queue.offer(new Pair(nextStr, nextPos));
                    map.put(nextStr, steps + 1);
                }
                swap(curCs, zeroPos, nextPos);
            }
        }
        return -1;
    }

    private void swap(char[] arr, int a, int b) {
        char t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}
